import java.util.ArrayList;

/**
 * Created by forcht on 2018/7/16.
 */
public class Solution {
    ArrayList<String> list=new ArrayList<>();
    ArrayList<Integer> tmp=new ArrayList<>();
    public ArrayList<String> restoreIpAddresses(String s) {
       dfs(s,0);
       return list;
    }

    public void dfs(String s,int cur){
        if(tmp.size()==4&&cur==s.length()){
            list.add(tmp.get(0)+"."+tmp.get(1)+"."+tmp.get(2)+"."+tmp.get(3));
            return;
        }
        for(int i=1;i<=3&&cur+i<=s.length();i++){
            Integer integer = Integer.valueOf(s.substring(cur, cur + i));
            if(integer<0||integer>255)continue;
            tmp.add(integer);
            dfs(s,cur+i);
            tmp.remove(tmp.size()-1);
            if (integer==0)i=4;
        }
    }

    public static void main(String[] args) {
       Solution solution=new Solution();
       System.out.println(solution.restoreIpAddresses("010010"));
    }
}
